package interview.tree;

import algorithm.model.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Leetcode 113
 *
 * 给定一个二叉树和目标和，找到所有从根节点到叶子节点路径总和等于给定目标的路径。
 * 注意：
 * 1）叶子节点是没有子节点的node
 * 2）返回结果是路径val的集合
 *
 *
 * Created by yzy on 2021-02-07 15:04
 */
public class PathSumII {


    public static void main(String[] args) {
        TreeNode tree = TreeNode.getTreeNode(new Integer[]{5,4,8,11,null,13,4,7,2,null,null,5,1});
        List<List<Integer>> lists = pathSum(tree, 22);
        System.out.println(lists);
    }

    /**
     * 思路，回溯法
     * @param root
     * @param targetSum
     * @return
     */
    public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> resList = new ArrayList<>();
        List<Integer> tmpList = new ArrayList<>();
        findPath(resList, tmpList, root, targetSum);
        return resList;
    }

    private static void findPath(List<List<Integer>> resList, List<Integer> tmpList, TreeNode node, int target){
        if(node==null) {
            return;
        }

        tmpList.add(node.val);
        if(node.left==null && node.right==null && node.val==target){
            resList.add(new ArrayList<>(tmpList));
        }else{
            findPath(resList, tmpList, node.left, target-node.val);
            findPath(resList, tmpList, node.right, target-node.val);
        }
        tmpList.remove(tmpList.size()-1);
    }
}
